package middle;

public class Solution_376 {

    public static void main(String[] args) {
        Solution_376 model = new Solution_376();
        System.out.println(model.wiggleMaxLength(new int[]{1}));
        System.out.println(model.wiggleMaxLength(new int[]{1, 2}));
        System.out.println(model.wiggleMaxLength(new int[]{2, 1}));
        System.out.println(model.wiggleMaxLength(new int[]{1,7,4,9,2,5}));
        System.out.println(model.wiggleMaxLength(new int[]{1,17,5,10,13,15,10,5,16,8}));
        System.out.println(model.wiggleMaxLength(new int[]{1,2,3,4,5,6,7,8,9}));
    }

    public int wiggleMaxLength(int[] nums) {
        // array[i][0]：包含第i个节点上摆的最大长度
        // array[i][1]：包含第i个节点下摆的最大长度
        int[][] array = new int[nums.length][2];
        int max = 1, pre_0_max = 1, pre_1_max = 1;
        for (int i = 0; i < nums.length; i++) {
            int temp_0_max = 0, temp_1_max = 0;
            if (i == 0) {
                temp_0_max++;
                temp_1_max++;
            } else {
                temp_0_max = pre_1_max + 1;
            }

            for (int j = i - 1; j >= 0; j--) {
                if (nums[i] > nums[j]) {
                    temp_0_max = Math.max(array[j][1], temp_0_max);
                } else if (nums[i] < nums[j]) {
                    temp_1_max = Math.max(array[j][0], temp_1_max);
                }
            }
            array[i] = new int[]{temp_0_max + 1, temp_1_max + 1};
            max = Math.max(max, Math.max(array[i][0], array[i][1]));
        }
        return max;
    }
}
